package com.mdnote.practice.binary_tree;

/**
 * @author Rhythm-2019
 * @version 1.0
 * @date 2020/9/30
 * @description 翻转二叉树
 */
public class LeetCode226 {
    public TreeNode invertTree(TreeNode root) {
        if (root == null) {
            return null;
        }
        return _reverse(root);
    }

    private TreeNode _reverse(TreeNode node) {
        // Terminator
        if (node.left == null && node.right == null) {
            return node;
        }
        // Process current logic
        TreeNode tmp = node.left;
        node.left = node.right;
        node.right = tmp;
        // drill down
        if (node.left != null) {
            _reverse(node.left);
        }
        if (node.right != null) {
            _reverse(node.right);
        }
        // restore current data
        return node;
    }

    public static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode(int x) { val = x; }
    }
}
